{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reconstruct Itinerary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #graph #eulerian-circuit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #图 #欧拉回路"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findItinerary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重新安排行程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一份航线列表 <code>tickets</code> ，其中 <code>tickets[i] = [from<sub>i</sub>, to<sub>i</sub>]</code> 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。</p>\n",
    "\n",
    "<p>所有这些机票都属于一个从 <code>JFK</code>（肯尼迪国际机场）出发的先生，所以该行程必须从 <code>JFK</code> 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，行程 <code>[\"JFK\", \"LGA\"]</code> 与 <code>[\"JFK\", \"LGB\"]</code> 相比就更小，排序更靠前。</li>\n",
    "</ul>\n",
    "\n",
    "<p>假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/14/itinerary1-graph.jpg\" style=\"width: 382px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>tickets = [[\"MUC\",\"LHR\"],[\"JFK\",\"MUC\"],[\"SFO\",\"SJC\"],[\"LHR\",\"SFO\"]]\n",
    "<strong>输出：</strong>[\"JFK\",\"MUC\",\"LHR\",\"SFO\",\"SJC\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/14/itinerary2-graph.jpg\" style=\"width: 222px; height: 230px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>tickets = [[\"JFK\",\"SFO\"],[\"JFK\",\"ATL\"],[\"SFO\",\"ATL\"],[\"ATL\",\"JFK\"],[\"ATL\",\"SFO\"]]\n",
    "<strong>输出：</strong>[\"JFK\",\"ATL\",\"JFK\",\"SFO\",\"ATL\",\"SFO\"]\n",
    "<strong>解释：</strong>另一种有效的行程是 [\"JFK\",\"SFO\",\"ATL\",\"JFK\",\"ATL\",\"SFO\"] ，但是它字典排序更大更靠后。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= tickets.length <= 300</code></li>\n",
    "\t<li><code>tickets[i].length == 2</code></li>\n",
    "\t<li><code>from<sub>i</sub>.length == 3</code></li>\n",
    "\t<li><code>to<sub>i</sub>.length == 3</code></li>\n",
    "\t<li><code>from<sub>i</sub></code> 和 <code>to<sub>i</sub></code> 由大写英文字母组成</li>\n",
    "\t<li><code>from<sub>i</sub> != to<sub>i</sub></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reconstruct-itinerary](https://leetcode.cn/problems/reconstruct-itinerary/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reconstruct-itinerary](https://leetcode.cn/problems/reconstruct-itinerary/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"MUC\",\"LHR\"],[\"JFK\",\"MUC\"],[\"SFO\",\"SJC\"],[\"LHR\",\"SFO\"]]', '[[\"JFK\",\"SFO\"],[\"JFK\",\"ATL\"],[\"SFO\",\"ATL\"],[\"ATL\",\"JFK\"],[\"ATL\",\"SFO\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution():\n",
    "    def findItinerary(self,tickets: List[List[str]]) -> List[str]:\n",
    "        paths = collections.defaultdict(list)   #由每个始发地为键，目的地为值组成的列表字典\n",
    "        for f,t in tickets:     #f，t分别为from，to，表示机票的始发地和目的地\n",
    "            paths[f].append(t)\n",
    "        for f in paths:\n",
    "            paths[f].sort(reverse=True)\n",
    "        res=[]\n",
    "        f_stack=['JFK']     #dfs所用的堆栈，用于回溯\n",
    "        while f_stack:\n",
    "            f=f_stack[-1]\n",
    "            if paths[f]:\n",
    "                f_stack.append(paths[f].pop())      #把t弹出，并添加到深搜堆栈中，把t作为f再进行深搜\n",
    "            else:\n",
    "                res.append(f)       #把没有t的f添加到结果列表\n",
    "                f_stack.pop()       #把没有t的f从深搜堆栈中弹出\n",
    "        return res[::-1]        #将结果列表倒序输出\n",
    "\n",
    "S = Solution()\n",
    "tickets = [[\"MUC\", \"LHR\"], [\"JFK\", \"MUC\"], [\"SFO\", \"SJC\"], [\"LHR\", \"SFO\"]]\n",
    "ans = S.findItinerary(tickets)\n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        combine = []\n",
    "        res = []\n",
    "        n = len(tickets)\n",
    "        tickets.sort()\n",
    "        used = [0]* n\n",
    "        def backtrack(combine,indx):\n",
    "            if len(combine) == n + 1:\n",
    "                res.append(combine[:])\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if len(res) == 1:\n",
    "                    break\n",
    "                if not combine and tickets[i][0] == \"JFK\" or (len(combine) > 0 and combine[-1] == tickets[i][0]):\n",
    "                    if not used[i]:\n",
    "                        if i > 0 and tickets[i] == tickets[i-1] and not used[i-1]:\n",
    "                            continue\n",
    "                        used[i] = 1\n",
    "                        if not combine:\n",
    "                            backtrack(combine + tickets[i],i)\n",
    "                        else:\n",
    "                            backtrack(combine + [tickets[i][1]],i)\n",
    "                        used[i] = 0\n",
    "        backtrack(combine,0)\n",
    "        res.sort()\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        _dict = defaultdict(list)\n",
    "        for ticket in tickets:\n",
    "            _dict[ticket[0]].append(ticket[1])\n",
    "\n",
    "        for key in _dict:\n",
    "            _dict[key].sort()\n",
    "\n",
    "        result = [\"JFK\"]\n",
    "\n",
    "        start = \"JFK\"\n",
    "\n",
    "        print(_dict)\n",
    "\n",
    "        def backtracking(start):\n",
    "            if (len(result) == (len(tickets) + 1)):\n",
    "                return True\n",
    "\n",
    "            for end in _dict[start]:\n",
    "                end = _dict[start].pop(0)\n",
    "                result.append(end)\n",
    "                if backtracking(end):\n",
    "                    return True\n",
    "                result.pop()\n",
    "                _dict[start].append(end)\n",
    "\n",
    "        backtracking(start)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        from collections import defaultdict\n",
    "        d = defaultdict(list)\n",
    "        for start, end in tickets:\n",
    "            d[start].append(end)\n",
    "        for key in d.keys():\n",
    "            d[key].sort()\n",
    "        print(d)\n",
    "\n",
    "        def dfs(start):\n",
    "            if len(res) == len(tickets) + 1:\n",
    "                return True\n",
    "            for i, end in enumerate(d[start]):\n",
    "                res.append(end)\n",
    "                d[start].pop(i)\n",
    "                if dfs(end):\n",
    "                    return True\n",
    "                res.pop()\n",
    "                d[start].insert(i, end)\n",
    "        \n",
    "        res = ['JFK']\n",
    "        dfs('JFK')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        from collections import defaultdict\n",
    "        ticket_dicts = defaultdict(list)\n",
    "        for ticket in tickets:\n",
    "            ticket_dicts[ticket[0]].append(ticket[1])\n",
    "        print(\"ticket_dicts:\",ticket_dicts)\n",
    "        #注意加入初始地址\n",
    "        result = [\"JFK\"] \n",
    "        def backtracking(start):\n",
    "            if len(result) == len(tickets)+1:\n",
    "                return True\n",
    "            if not ticket_dicts[start]:\n",
    "                return False\n",
    "            #sort \n",
    "            ticket_dicts[start].sort()\n",
    "            #注意修改list的遍历问题\n",
    "            #这个地方为何是append到后面呢\n",
    "            for _ in ticket_dicts[start]:\n",
    "                #必须及时删除，避免出现死循环\n",
    "                print(\"before0 start:\",start,\",end:\",ticket_dicts[start][0],\",tick :\",ticket_dicts[start])\n",
    "                end = ticket_dicts[start].pop(0)\n",
    "                print(\"before start:\",start,\",end:\",end,\",tick :\",ticket_dicts[start])\n",
    "                result.append(end)\n",
    "                if backtracking(end):\n",
    "                    return True  \n",
    "                result.pop() \n",
    "                #这个地方为何是append到后面呢\n",
    "                ticket_dicts[start].append(end)\n",
    "                print(\"after start:\",start,\",end:\",end,\",tick :\",ticket_dicts[start])\n",
    "            return False \n",
    "        backtracking(\"JFK\")\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        dest = defaultdict(list)\n",
    "        for start, end in sorted(tickets)[::-1]:\n",
    "            dest[start].append(end)\n",
    "        \n",
    "        routes = []\n",
    "        st = ['JFK']\n",
    "        while st:\n",
    "            while dest[st[-1]]:\n",
    "                st.append(dest[st[-1]].pop())\n",
    "            routes.append(st.pop())\n",
    "    \n",
    "        return routes[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中\n",
    "        \n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序\n",
    "        \n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  # 调用回溯函数开始搜索路径\n",
    "        return result[::-1]  # 返回逆序的行程路径\n",
    "    \n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  # 当机场还有可到达的机场时\n",
    "            next_airport = targets[airport].pop()  # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport)  # 将当前机场添加到行程路径中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution():\n",
    "    def findItinerary(self,tickets: List[List[str]]) -> List[str]:\n",
    "        paths = collections.defaultdict(list)   #由每个始发地为键，目的地为值组成的列表字典\n",
    "        for f,t in tickets:     #f，t分别为from，to，表示机票的始发地和目的地\n",
    "            paths[f].append(t)\n",
    "        for f in paths:\n",
    "            paths[f].sort(reverse=True)\n",
    "        res=[]\n",
    "        f_stack=['JFK']     #dfs所用的堆栈，用于回溯\n",
    "        while f_stack:\n",
    "            f=f_stack[-1]\n",
    "            if paths[f]:\n",
    "                f_stack.append(paths[f].pop())      #把t弹出，并添加到深搜堆栈中，把t作为f再进行深搜\n",
    "            else:\n",
    "                res.append(f)       #把没有t的f添加到结果列表\n",
    "                f_stack.pop()       #把没有t的f从深搜堆栈中弹出\n",
    "        return res[::-1]        #将结果列表倒序输出\n",
    "\n",
    "S = Solution()\n",
    "tickets = [[\"MUC\", \"LHR\"], [\"JFK\", \"MUC\"], [\"SFO\", \"SJC\"], [\"LHR\", \"SFO\"]]\n",
    "ans = S.findItinerary(tickets)\n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中\n",
    "        \n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序\n",
    "        \n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  # 调用回溯函数开始搜索路径\n",
    "        return result[::-1]  # 返回逆序的行程路径\n",
    "    \n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  # 当机场还有可到达的机场时\n",
    "            next_airport = targets[airport].pop()  # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport)  # 将当前机场添加到行程路径中\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中\n",
    "        \n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序\n",
    "        \n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  # 调用回溯函数开始搜索路径\n",
    "        return result[::-1]  # 返回逆序的行程路径\n",
    "    \n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  # 当机场还有可到达的机场时\n",
    "            next_airport = targets[airport].pop()  # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport)  # 将当前机场添加到行程路径中\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        target=defaultdict(list)\n",
    "\n",
    "        for ticket in tickets:\n",
    "            target[ticket[0]].append(ticket[1])\n",
    "        \n",
    "        for key in target:\n",
    "            target[key].sort(reverse=True)\n",
    "        \n",
    "        result=[]\n",
    "        self.backtracking('JFK',target,result)\n",
    "        return result[::-1]\n",
    "    \n",
    "    def backtracking(self,airport,target,result):\n",
    "        while target[airport]:\n",
    "            next_airport=target[airport].pop()\n",
    "            self.backtracking(next_airport,target,result)\n",
    "        result.append(airport)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "#         res,path=[],[\"JFK\"]\n",
    "#         used = [0]*len(tickets)\n",
    "#         tickets.sort()\n",
    "#         def backtracking(cur):\n",
    "#             if len(path) == len(tickets)+1:\n",
    "#                 res.append(path[:])\n",
    "#                 return True\n",
    "#             for i,ticket in enumerate(tickets):\n",
    "#                 if ticket[0]==cur and used[i]==0:\n",
    "#                     path.append(ticket[1])\n",
    "#                     used[i]=1\n",
    "#                     state = backtracking(ticket[1])\n",
    "#                     path.pop()\n",
    "#                     used[i]=0\n",
    "#                     if state:return True\n",
    "                \n",
    "#         backtracking(\"JFK\")\n",
    "#         return res[0]\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中\n",
    "        \n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序\n",
    "        \n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  # 调用回溯函数开始搜索路径\n",
    "        return result[::-1]  # 返回逆序的行程路径\n",
    "    \n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  # 当机场还有可到达的机场时\n",
    "            next_airport = targets[airport].pop()  # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport)  # 将当前机场添加到行程路径中\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "\n",
    "\n",
    "        vec = collections.defaultdict(list)\n",
    "        for depart, arrive in tickets:\n",
    "            vec[depart].append(arrive)\n",
    "        for key in vec:\n",
    "            vec[key].sort(reverse=True)\n",
    "        \n",
    "        stack = list()\n",
    "        ans=[]\n",
    "        stack.append('JFK')\n",
    "        while stack:\n",
    "            curr=stack[-1]\n",
    "            if not vec[curr]:\n",
    "                ans.append(stack.pop())\n",
    "            else:\n",
    "                p=vec[curr].pop()\n",
    "                stack.append(p)\n",
    "        return ans[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        \"\"\"回溯，使用字典，逆序\"\"\"\n",
    "        from collections import defaultdict\n",
    "        targets = defaultdict(list) # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1]) # 将机票输入到字典中\n",
    "\n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True) # 对到达机场列表进行字母逆序排序\n",
    "\n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result) # 调用回溯函数开始搜索路径\n",
    "        return result[::-1] # 返回逆序的行程路径\n",
    "\n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]: # 当机场还有可达到的机场时\n",
    "            next_airport = targets[airport].pop() # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result) # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport) # 将当前机场添加到行程路径中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中\n",
    "        \n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序\n",
    "        \n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  # 调用回溯函数开始搜索路径\n",
    "        return result[::-1]  # 返回逆序的行程路径\n",
    "    \n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  # 当机场还有可到达的机场时\n",
    "            next_airport = targets[airport].pop()  # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport)  # 将当前机场添加到行程路径中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        targets = defaultdict(list)  # 构建机场字典\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])\n",
    "        for airport in targets:\n",
    "            targets[airport].sort()  # 对目的地列表进行排序\n",
    "\n",
    "        path = [\"JFK\"]  # 起始机场为\"JFK\"\n",
    "        self.backtracking(targets, path, len(tickets))\n",
    "        return path\n",
    "\n",
    "    def backtracking(self, targets, path, ticketNum):\n",
    "        if len(path) == ticketNum + 1:\n",
    "            return True  # 找到有效行程\n",
    "\n",
    "        airport = path[-1]  # 当前机场\n",
    "        destinations = targets[airport]  # 当前机场可以到达的目的地列表\n",
    "        for i, dest in enumerate(destinations):\n",
    "            if i > 0 and destinations[i] == destinations[i - 1]:\n",
    "                continue\n",
    "            targets[airport].pop(i)  # 标记已使用的机票\n",
    "            path.append(dest)  # 添加目的地到路径\n",
    "            if self.backtracking(targets, path, ticketNum):\n",
    "                return True  # 找到有效行程\n",
    "            targets[airport].insert(i, dest)  # 回溯，恢复机票\n",
    "            path.pop()  # 移除目的地\n",
    "        return False  # 没有找到有效行程"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中\n",
    "        \n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序\n",
    "        \n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  # 调用回溯函数开始搜索路径\n",
    "        return result[::-1]  # 返回逆序的行程路径\n",
    "    \n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  # 当机场还有可到达的机场时\n",
    "            next_airport = targets[airport].pop()  # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport)  # 将当前机场添加到行程路径中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中\n",
    "        \n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序\n",
    "        \n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  # 调用回溯函数开始搜索路径\n",
    "        return result[::-1]  # 返回逆序的行程路径\n",
    "    \n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  # 当机场还有可到达的机场时\n",
    "            next_airport = targets[airport].pop()  # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport)  # 将当前机场添加到行程路径中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.combs = []\n",
    "        self.path = []\n",
    "        self.used = []\n",
    "        self.find = False\n",
    "        \n",
    "    def traceback(self, tickets: list[list[str]], departure) -> None:\n",
    "        if len(self.path) == len(tickets):\n",
    "            self.path.append(departure)\n",
    "            self.combs = list(self.path)\n",
    "            self.find = True\n",
    "            self.path.pop()\n",
    "            return\n",
    "        for i in range(0, len(tickets)):\n",
    "            if not (i > 0 and tickets[i-1] == tickets[i] and self.used[i-1] == 0):\n",
    "                # print('in了'):\n",
    "                # print('in了')\n",
    "                if tickets[i][0] == departure and self.used[i] == 0:\n",
    "                    self.path.append(tickets[i][0]) \n",
    "                    self.used[i] = 1\n",
    "                    self.traceback(tickets, tickets[i][1])\n",
    "                    self.used[i] = 0\n",
    "                    self.path.pop()\n",
    "                    if self.find:\n",
    "                        return\n",
    "        \n",
    "\n",
    "    def findItinerary(self, tickets: list[list[str]]) -> list[str]:\n",
    "        tickets.sort()\n",
    "        self.used = [0] * len(tickets)\n",
    "        self.traceback(tickets, 'JFK')\n",
    "        return self.combs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "#         targets = defaultdict(list)  # 构建机场字典\n",
    "#         for ticket in tickets:\n",
    "#             targets[ticket[0]].append(ticket[1])\n",
    "#         for airport in targets:\n",
    "#             targets[airport].sort()  # 对目的地排序\n",
    "        \n",
    "#         self.path = ['JFK']\n",
    "#         self.backtracking(len(tickets), targets)\n",
    "#         return self.path\n",
    "            \n",
    "#     def backtracking(self, n, targets):\n",
    "#         if len(self.path) == n + 1:\n",
    "#             return True\n",
    "#         cur = self.path[-1]\n",
    "#         for i, tar in enumerate(targets[cur]):\n",
    "#             # 删除已经使用的机票\n",
    "#             targets[cur].pop(i)\n",
    "#             self.path.append(tar)\n",
    "#             state = self.backtracking(n, targets)\n",
    "#             if state:\n",
    "#                 return True\n",
    "#             targets[cur].insert(i, tar)\n",
    "#             self.path.pop()\n",
    "#         return False\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中\n",
    "        \n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序\n",
    "        \n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  # 调用回溯函数开始搜索路径\n",
    "        return result[::-1]  # 返回逆序的行程路径\n",
    "    \n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  # 当机场还有可到达的机场时\n",
    "            next_airport = targets[airport].pop()  # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport)  # 将当前机场添加到行程路径中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中\n",
    "        \n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序\n",
    "        \n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  # 调用回溯函数开始搜索路径\n",
    "        return result[::-1]  # 返回逆序的行程路径\n",
    "    \n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  # 当机场还有可到达的机场时\n",
    "            next_airport = targets[airport].pop()  # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport)  # 将当前机场添加到行程路径中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中\n",
    "        \n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序\n",
    "        \n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  # 调用回溯函数开始搜索路径\n",
    "        return result[::-1]  # 返回逆序的行程路径\n",
    "    \n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  # 当机场还有可到达的机场时\n",
    "            next_airport = targets[airport].pop()  # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport)  # 将当前机场添加到行程路径中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def  __init__(self):\n",
    "        self.path = None\n",
    "        self.result = None\n",
    "        self.used = None\n",
    "        self.n = None\n",
    "\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        tickets.sort()\n",
    "        self.n = len(tickets)\n",
    "        self.used = [False] * self.n\n",
    "        self.path = [\"JFK\"]\n",
    "        self.backtracking(tickets, \"JFK\")\n",
    "        return self.result\n",
    "    \n",
    "    def backtracking(self, tickets, cur_airport):\n",
    "        if len(self.path) == self.n + 1:\n",
    "            self.result = self.path[:]\n",
    "            return True\n",
    "        \n",
    "        ignore = set()\n",
    "        for i, ticket in enumerate(tickets):\n",
    "            start, destination = ticket\n",
    "            # 是从当前机场出发并且机票没有使用过\n",
    "            if start == cur_airport and self.used[i] == False and (start, destination) not in ignore:\n",
    "                self.path.append(destination)\n",
    "                self.used[i] = True\n",
    "                is_found = self.backtracking(tickets, destination)\n",
    "                if is_found:\n",
    "                    return True\n",
    "                else:\n",
    "                    ignore.add((start, destination))\n",
    "                self.path.pop()\n",
    "                self.used[i] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        # 机场到目的地的映射\n",
    "        targets = defaultdict(list)\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])\n",
    "\n",
    "        # 逆序排序下\n",
    "        for airport in targets:\n",
    "            targets[airport].sort(reverse=True)\n",
    "\n",
    "        res = []\n",
    "        self.dfs(targets, \"JFK\", res)\n",
    "        return res[::-1]\n",
    "\n",
    "    def dfs(self, targets, airport, res):\n",
    "        while targets[airport]:\n",
    "            dest = targets[airport].pop()\n",
    "            self.dfs(targets, dest, res)\n",
    "        res.append(airport)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中\n",
    "        \n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序\n",
    "        \n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  # 调用回溯函数开始搜索路径\n",
    "        return result[::-1]  # 返回逆序的行程路径\n",
    "    \n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  # 当机场还有可到达的机场时\n",
    "            next_airport = targets[airport].pop()  # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport)  # 将当前机场添加到行程路径中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list) \n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  \n",
    "        \n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True) \n",
    "        \n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  \n",
    "        return result[::-1]  \n",
    "    \n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  \n",
    "            next_airport = targets[airport].pop()  \n",
    "            self.backtracking(next_airport, targets, result) \n",
    "        result.append(airport)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.combs = []\n",
    "        self.path = []\n",
    "        self.used = []\n",
    "        self.find = False\n",
    "        \n",
    "    def traceback(self, tickets: list[list[str]], departure) -> None:\n",
    "        if len(self.path) == len(tickets):\n",
    "            self.path.append(departure)\n",
    "            self.combs = list(self.path)\n",
    "            self.find = True\n",
    "            self.path.pop()\n",
    "            return\n",
    "        for i in range(0, len(tickets)):\n",
    "            if tickets[i][0] == departure and self.used[i] == 0 and not (i > 0 and tickets[i-1] == tickets[i] and self.used[i-1] == 0):\n",
    "                # print('in了'):\n",
    "                # print('in了')\n",
    "                self.path.append(tickets[i][0]) \n",
    "                self.used[i] = 1\n",
    "                self.traceback(tickets, tickets[i][1])\n",
    "                self.used[i] = 0\n",
    "                self.path.pop()\n",
    "                if self.find:\n",
    "                    return\n",
    "        \n",
    "\n",
    "    def findItinerary(self, tickets: list[list[str]]) -> list[str]:\n",
    "        tickets.sort()\n",
    "        self.used = [0] * len(tickets)\n",
    "        self.traceback(tickets, 'JFK')\n",
    "        return self.combs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        # 构建图\n",
    "        graph = {}\n",
    "        for ticket in tickets:\n",
    "            from_city, to_city = ticket\n",
    "            if from_city not in graph:\n",
    "                graph[from_city] = []\n",
    "            graph[from_city].append(to_city)\n",
    "        \n",
    "        # 对目的地列表按字典序排序\n",
    "        for city in graph:\n",
    "            graph[city].sort()\n",
    "        \n",
    "        # DFS遍历图\n",
    "        def dfs(city, result):\n",
    "            if city not in graph:\n",
    "                result.append(city)\n",
    "                return result\n",
    "            while graph[city]:\n",
    "                next_city = graph[city].pop(0)\n",
    "                result = dfs(next_city, result)\n",
    "            result.append(city)\n",
    "            return result\n",
    "        \n",
    "        # 结果列表\n",
    "        result = dfs(\"JFK\", [])\n",
    "        \n",
    "        # 反转结果列表\n",
    "        result.reverse()\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 回溯 使用used数组\n",
    "# class Solution:\n",
    "#     def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "#         tickets.sort() # 先排序，这样一旦找到第一个可行路径，一定是字母排序最小的\n",
    "#         used = [0] * len(tickets)\n",
    "#         path = ['JFK']\n",
    "#         results = []\n",
    "#         self.backtracking(tickets, used, path, 'JFK', results)\n",
    "#         return results[0]\n",
    "    \n",
    "#     def backtracking(self, tickets, used, path, cur, results):\n",
    "#         if len(path) == len(tickets) + 1:  # 终止条件：路径长度等于机票数量+1\n",
    "#             results.append(path[:])  # 将当前路径添加到结果列表\n",
    "#             return True\n",
    "        \n",
    "#         for i, ticket in enumerate(tickets):  # 遍历机票列表\n",
    "#             if ticket[0] == cur and used[i] == 0:  # 找到起始机场为cur且未使用过的机票\n",
    "#                 used[i] = 1  # 标记该机票为已使用\n",
    "#                 path.append(ticket[1])  # 将到达机场添加到路径中\n",
    "#                 state = self.backtracking(tickets, used, path, ticket[1], results)  # 递归搜索\n",
    "#                 path.pop()  # 回溯，移除最后添加的到达机场\n",
    "#                 used[i] = 0  # 标记该机票为未使用\n",
    "#                 if state:\n",
    "#                     return True  # 只要找到一个可行路径就返回，不继续搜索\n",
    "\n",
    "# from collections import defaultdict\n",
    "\n",
    "# class Solution:\n",
    "#     def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "#         targets = defaultdict(list)  # 构建机场字典\n",
    "#         for ticket in tickets:\n",
    "#             targets[ticket[0]].append(ticket[1])\n",
    "#         for airport in targets:\n",
    "#             targets[airport].sort()  # 对目的地列表进行排序\n",
    "\n",
    "#         path = [\"JFK\"]  # 起始机场为\"JFK\"\n",
    "#         self.backtracking(targets, path, len(tickets))\n",
    "#         return path\n",
    "\n",
    "#     def backtracking(self, targets, path, ticketNum):\n",
    "#         if len(path) == ticketNum + 1:\n",
    "#             return True  # 找到有效行程\n",
    "\n",
    "#         airport = path[-1]  # 当前机场\n",
    "#         destinations = targets[airport]  # 当前机场可以到达的目的地列表\n",
    "#         for i, dest in enumerate(destinations):\n",
    "#             targets[airport].pop(i)  # 标记已使用的机票\n",
    "#             path.append(dest)  # 添加目的地到路径\n",
    "#             if self.backtracking(targets, path, ticketNum):\n",
    "#                 return True  # 找到有效行程\n",
    "#             targets[airport].insert(i, dest)  # 回溯，恢复机票\n",
    "#             path.pop()  # 移除目的地\n",
    "#         return False  # 没有找到有效行程\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中\n",
    "        \n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序\n",
    "        \n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  # 调用回溯函数开始搜索路径\n",
    "        return result[::-1]  # 返回逆序的行程路径\n",
    "    \n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  # 当机场还有可到达的机场时\n",
    "            next_airport = targets[airport].pop()  # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport)  # 将当前机场添加到行程路径中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        targets = defaultdict(list)  # 创建默认字典，用于存储机场映射关系\n",
    "        for ticket in tickets:\n",
    "            targets[ticket[0]].append(ticket[1])  # 将机票输入到字典中\n",
    "\n",
    "        for key in targets:\n",
    "            targets[key].sort(reverse=True)  # 对到达机场列表进行字母逆序排序\n",
    "\n",
    "        result = []\n",
    "        self.backtracking(\"JFK\", targets, result)  # 调用回溯函数开始搜索路径\n",
    "        return result[::-1]  # 返回逆序的行程路径\n",
    "\n",
    "    def backtracking(self, airport, targets, result):\n",
    "        while targets[airport]:  # 当机场还有可到达的机场时\n",
    "            next_airport = targets[airport].pop()  # 弹出下一个机场\n",
    "            self.backtracking(next_airport, targets, result)  # 递归调用回溯函数进行深度优先搜索\n",
    "        result.append(airport)  # 将当前机场添加到行程路径中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "\n",
    "        # n = len(tickets)\n",
    "        # tickets.sort(key = lambda x: x[1])\n",
    "\n",
    "        # m = {}\n",
    "        # for idx, (f, t) in enumerate(tickets):\n",
    "        #     if f in m.keys():\n",
    "        #         m[f].append((t, idx))\n",
    "        #     else:\n",
    "        #         m[f] = [(t, idx)]\n",
    "\n",
    "        # def backtracking(state, used, res):\n",
    "        #     if len(state) == n + 1:\n",
    "        #         res.append(list(state))\n",
    "        #         return\n",
    "\n",
    "        #     next_city = m.get(state[-1], [])\n",
    "\n",
    "        #     for i, idx in next_city:\n",
    "        #         if not used[idx] and len(res) == 0:\n",
    "        #             used[idx] = True\n",
    "        #             state.append(i)\n",
    "        #             backtracking(state, used, res)\n",
    "                    \n",
    "        #             state.pop()\n",
    "        #             used[idx] = False\n",
    "\n",
    "        # used = [False] * n\n",
    "        # res = []\n",
    "        # backtracking([\"JFK\"], used, res)\n",
    "\n",
    "        # return res[0]\n",
    "        def dfs(curr: str):\n",
    "            while vec[curr]:\n",
    "                tmp = heapq.heappop(vec[curr])\n",
    "                dfs(tmp)\n",
    "            stack.append(curr)\n",
    "\n",
    "        vec = collections.defaultdict(list)\n",
    "        for depart, arrive in tickets:\n",
    "            vec[depart].append(arrive)\n",
    "        for key in vec:\n",
    "            heapq.heapify(vec[key])\n",
    "        \n",
    "        stack = list()\n",
    "        dfs(\"JFK\")\n",
    "        return stack[::-1]\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        targets = defaultdict(list)\n",
    "        for t in tickets:\n",
    "            targets[t[0]].append(t[1])\n",
    "        for a in targets:\n",
    "            targets[a].sort(reverse=True)\n",
    "        def backtracking(airport, path):\n",
    "            while targets[airport]:\n",
    "                next = targets[airport].pop()\n",
    "                backtracking(next, path)\n",
    "            path.append(airport)\n",
    "        path = []\n",
    "        backtracking('JFK', path)\n",
    "        return path[::-1]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        graph_table = defaultdict(list)\n",
    "        for start, end in tickets:\n",
    "            graph_table[start].append(end)\n",
    "        for city in graph_table:\n",
    "            graph_table[city].sort()\n",
    "        \n",
    "        ans = []\n",
    "        def dfs(start):\n",
    "            while graph_table[start]:\n",
    "                dfs(graph_table[start].pop(0))\n",
    "            ans.insert(0, start)\n",
    "        dfs('JFK')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        def dfs(start):\n",
    "            while depart[start]:\n",
    "                next_city = depart[start].pop()\n",
    "                dfs(next_city)\n",
    "            res.append(start)\n",
    "\n",
    "        depart = defaultdict(list)\n",
    "        for d, a in tickets:\n",
    "            depart[d].append(a)\n",
    "        for item in depart.values():\n",
    "            item.sort(reverse=True)\n",
    "        res = []\n",
    "        dfs('JFK')\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        ad=collections.defaultdict(list)\n",
    "\n",
    "        for s,e in tickets:\n",
    "            ad[s].append(e)\n",
    "        \n",
    "        for x in ad:\n",
    "            ad[x]=sorted(ad[x],reverse=True)\n",
    "        ans=[]\n",
    "\n",
    "        def dfs(cur):\n",
    "            nonlocal ans \n",
    "            while ad[cur]:\n",
    "                nex=ad[cur].pop()\n",
    "                dfs(nex)\n",
    "            ans=[cur]+ans\n",
    "            return \n",
    "        dfs(\"JFK\")\n",
    "        return ans \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        graph_table = defaultdict(list)\n",
    "        for start, end in tickets:\n",
    "            graph_table[start].append(end)\n",
    "        for city in graph_table:\n",
    "            graph_table[city].sort()\n",
    "        \n",
    "        ans = []\n",
    "        def dfs(start):\n",
    "            while graph_table[start]:\n",
    "                dfs(graph_table[start].pop(0))\n",
    "            ans.insert(0, start)\n",
    "        dfs('JFK')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "\n",
    "#         def dfs(begin, tickets, size, used, path, res):\n",
    "\n",
    "\n",
    "#             if used == [True] * size:\n",
    "#                 if not res:\n",
    "#                     res[:] = path\n",
    "#                 else:\n",
    "#                     for str_res, str_path in zip(res[1:], path[1:]):\n",
    "#                         flag = False\n",
    "#                         for i, j in zip(str_res, str_path):\n",
    "#                             ord_res = ord(i)\n",
    "#                             ord_path = ord(j)\n",
    "#                             if ord_res > ord_path:\n",
    "#                                 res[:] = path\n",
    "#                                 flag = True\n",
    "#                                 break\n",
    "\n",
    "#                             elif ord_res < ord_path:\n",
    "#                                 flag = True\n",
    "#                                 break\n",
    "#                         if flag:\n",
    "#                             break\n",
    "\n",
    "#             for idx in range(size):\n",
    "#                 if tickets[idx][0] != begin or used[idx] == True:\n",
    "#                     continue\n",
    "#                 used[idx] = True\n",
    "#                 dfs(tickets[idx][1], tickets, size, used, path + [tickets[idx][1]], res)\n",
    "#                 used[idx] = False\n",
    "        \n",
    "#         size = len(tickets)\n",
    "#         used = [False] * size\n",
    "#         path = ['JFK']\n",
    "#         res = []\n",
    "#         dfs('JFK', tickets, size, used, path, res)\n",
    "#         return res\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        def dfs(curr: str):\n",
    "            while vec[curr]:\n",
    "                tmp = heapq.heappop(vec[curr])\n",
    "                dfs(tmp)\n",
    "            stack.append(curr)\n",
    "\n",
    "        vec = collections.defaultdict(list)\n",
    "        for depart, arrive in tickets:\n",
    "            vec[depart].append(arrive)\n",
    "        for key in vec:\n",
    "            heapq.heapify(vec[key])\n",
    "        \n",
    "        stack = list()\n",
    "        dfs(\"JFK\")\n",
    "        return stack[::-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        d = collections.defaultdict(list)   #邻接表\n",
    "        for f, t in tickets:\n",
    "            d[f] += [t]             #路径存进邻接表\n",
    "        for f in d:\n",
    "            d[f].sort(reverse=True)\n",
    "        ans = []\n",
    "        def dfs(f):\n",
    "            while d[f]:\n",
    "                dfs(d[f].pop())  #路径检索\n",
    "            ans.append(f)\n",
    "        dfs('JFK')\n",
    "        return ans[:: -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        graph = defaultdict(list)\n",
    "        for ticket in tickets:\n",
    "            src, dest = ticket\n",
    "            graph[src].append(dest)\n",
    "        \n",
    "        for src in graph:\n",
    "            graph[src].sort()\n",
    "        \n",
    "        def dfs(node):\n",
    "            while graph[node]:\n",
    "                dfs(graph[node].pop(0))\n",
    "            result.append(node)\n",
    "        \n",
    "        result = []\n",
    "        dfs(\"JFK\")\n",
    "        return result[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        ticketDicts = {}\n",
    "        for src, trg in tickets:\n",
    "            if src not in ticketDicts:\n",
    "                ticketDicts[src] = []\n",
    "            ticketDicts[src].append(trg)\n",
    "        for src in ticketDicts:\n",
    "            ticketDicts[src].sort(reverse=True)\n",
    "        \n",
    "        path = []\n",
    "        def _DFS(src):\n",
    "            while src in ticketDicts and ticketDicts[src]:\n",
    "                trg = ticketDicts[src].pop()\n",
    "                _DFS(trg)\n",
    "            path.append(src)\n",
    "        \n",
    "        _DFS('JFK')\n",
    "        path.reverse()\n",
    "        return path\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        # ticks = collections.defaultdict(list)\n",
    "        # for fr, to in tickets:\n",
    "        #     ticks[fr].append(to)\n",
    "\n",
    "        # def dfs(state, fr, tcks, res):\n",
    "        #     if len(state) == len(tickets) + 1:\n",
    "        #         res.append(state[:])\n",
    "        #         return True\n",
    "        #     for to in sorted(tcks[fr]):\n",
    "        #         state.append(to)\n",
    "        #         tcks[fr].remove(to)\n",
    "        #         dfs(state, to, tcks, res)\n",
    "\n",
    "        #         tcks[fr].append(to)\n",
    "        #         state.pop()\n",
    "        # res = []\n",
    "        # dfs([\"JFK\"], \"JFK\", ticks, res)\n",
    "        # return res[0]\n",
    "        def dfs(curr: str):\n",
    "            while vec[curr]:\n",
    "                tmp = heapq.heappop(vec[curr])\n",
    "                dfs(tmp)\n",
    "            stack.append(curr)\n",
    "\n",
    "        vec = collections.defaultdict(list)\n",
    "        for depart, arrive in tickets:\n",
    "            vec[depart].append(arrive)\n",
    "        for key in vec:\n",
    "            heapq.heapify(vec[key])\n",
    "          \n",
    "        stack = list()\n",
    "        dfs(\"JFK\")\n",
    "        return stack[::-1]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        # 构建图的邻接表\n",
    "        graph = {}\n",
    "        for ticket in tickets:\n",
    "            from_city, to_city = ticket\n",
    "            if from_city not in graph:\n",
    "                graph[from_city] = []\n",
    "            graph[from_city].append(to_city)\n",
    "        \n",
    "        # 对邻接表中的目的地进行排序\n",
    "        for city in graph:\n",
    "            graph[city].sort(reverse=True)\n",
    "        \n",
    "        # 深度优先搜索\n",
    "        itinerary = []\n",
    "        def dfs(city):\n",
    "            while city in graph and graph[city]:\n",
    "                dfs(graph[city].pop())\n",
    "            itinerary.append(city)\n",
    "        \n",
    "        dfs(\"JFK\")\n",
    "        \n",
    "        # 反转行程路径，得到最小的行程组合\n",
    "        return itinerary[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        if len(tickets) == 0 : return []\n",
    "        res = []\n",
    "        map = defaultdict(list)\n",
    "        for ticket in tickets:\n",
    "            dep, des = ticket[0],ticket[1]\n",
    "            map[dep].append(des)\n",
    "        for key,value in map.items():\n",
    "            map[key] = sorted(value)\n",
    "        \n",
    "        def dfs(src):\n",
    "            next  = map.get(src,[])\n",
    "            while next:\n",
    "                des = next.pop(0)\n",
    "                dfs(des)\n",
    "            res.insert(0, src)\n",
    "            return\n",
    "        dfs(\"JFK\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        d = collections.defaultdict(list)\n",
    "        for f, t in tickets:\n",
    "            d[f] += [t]\n",
    "        \n",
    "        for f in d:\n",
    "            d[f].sort()\n",
    "        \n",
    "        ans = []\n",
    "        def dfs(f):\n",
    "            while d[f]:\n",
    "                dfs(d[f].pop(0))\n",
    "            ans.insert(0, f)\n",
    "        dfs('JFK')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        # 定义一个字典，记录每个机场的邻接机场，即到达该机场后还可以到达哪些机场\n",
    "        edges = collections.defaultdict(list)\n",
    "        for start, end in tickets:\n",
    "            edges[start].append(end)\n",
    "        # 将字典中的所有列表最小堆话（变成最小优先级队列）\n",
    "        for key in edges.keys():\n",
    "            heapq.heapify(edges[key])\n",
    "        res = []\n",
    "\n",
    "        def search(cur):\n",
    "            # 每次沿着一条边一直搜索到终点，然后反向将搜索路程上的所有节点都入栈\n",
    "            while edges[cur]:\n",
    "                temp = heapq.heappop(edges[cur])\n",
    "                search(temp)\n",
    "            # 从搜索的终点开始将整条路线上的所有节点入栈\n",
    "            res.append(cur)\n",
    "\n",
    "        search('JFK')\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        target = defaultdict(list)\n",
    "        for ticket in tickets:\n",
    "            target[ticket[0]].append(ticket[1])\n",
    "        for key in target:\n",
    "            heapq.heapify(target[key])\n",
    "        res = []\n",
    "        def dfs(cur):\n",
    "            while target[cur]:\n",
    "                nextcur = heapq.heappop(target[cur])\n",
    "                dfs(nextcur)\n",
    "            res.append(cur)\n",
    "        dfs('JFK')\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = []\n",
    "        self.path = []\n",
    "\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        self.path.append(\"JFK\")\n",
    "        return self.backtracking(\"JFK\", sorted(tickets))\n",
    "\n",
    "    def backtracking(self, target: str, tickets: List[List[str]]):\n",
    "        if not tickets:\n",
    "            return self.path\n",
    "\n",
    "        used = set()\n",
    "\n",
    "        for i, pair in enumerate(tickets):\n",
    "            if pair[0] != target:\n",
    "                continue\n",
    "            if pair[1] in used:\n",
    "                continue\n",
    "            used.add(pair[1])\n",
    "\n",
    "            self.path.append(pair[1])\n",
    "            path = self.backtracking(pair[1], tickets[:i] + tickets[i + 1 :])\n",
    "            if path:\n",
    "                return path\n",
    "            self.path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        neighbors = defaultdict(list)\n",
    "        for depart, arrival in tickets:\n",
    "            neighbors[depart].append(arrival)\n",
    "        \n",
    "        for k in neighbors:\n",
    "            heapify(neighbors[k])\n",
    "        \n",
    "        def helper(cur):\n",
    "            while neighbors[cur]:\n",
    "                n = heappop(neighbors[cur])\n",
    "                helper(n)\n",
    "            res.append(cur)\n",
    "\n",
    "        res = []\n",
    "        helper(\"JFK\")\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        neighbors = defaultdict(list)\n",
    "        res = []\n",
    "\n",
    "        for a, b in tickets:\n",
    "            neighbors[a].append(b)\n",
    "        \n",
    "        for k in neighbors:\n",
    "            heapify(neighbors[k])\n",
    "\n",
    "        def helper(cur):\n",
    "            while neighbors[cur]:\n",
    "                n = heappop(neighbors[cur])\n",
    "                helper(n)\n",
    "            res.append(cur)\n",
    "        \n",
    "        helper(\"JFK\")\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ans = []\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        rec = dict()\n",
    "        n = len(tickets)\n",
    "        for dep, dest in tickets:\n",
    "            if dep not in rec:\n",
    "                rec[dep] = []\n",
    "            rec[dep].append(dest)\n",
    "        for value in rec.values():\n",
    "            value.sort()\n",
    "        def dfs(cur, res, i):\n",
    "            if i == 0:\n",
    "                self.ans = res\n",
    "                return\n",
    "            if cur not in rec:\n",
    "                return\n",
    "            s = len(rec[cur])\n",
    "            if s == 0:\n",
    "                return\n",
    "            last = None\n",
    "            for j in range(s):\n",
    "                if len(self.ans) > 0:\n",
    "                    break\n",
    "                item = rec[cur][j]\n",
    "                if last == item:\n",
    "                    continue\n",
    "                last = item\n",
    "                rec[cur] = rec[cur][:j] + rec[cur][j+1:]\n",
    "                dfs(item, res + [item], i - 1)\n",
    "                rec[cur] = rec[cur][:j] + [item] + rec[cur][j:]\n",
    "        dfs(\"JFK\", [\"JFK\"], n)\n",
    "        return self.ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        def dfs(ticket):\n",
    "            if (ticket not in Sons):\n",
    "                St.append(ticket)\n",
    "                return 0\n",
    "            while (Sons[ticket]):\n",
    "                tmp = Sons[ticket][0]\n",
    "                Sons[ticket].pop(0)\n",
    "                dfs(tmp)\n",
    "            St.append(ticket)\n",
    "            return 0\n",
    "\n",
    "        Sons = {}\n",
    "        n = len(tickets)\n",
    "        for ticket in tickets:\n",
    "            if (ticket[0] in Sons):\n",
    "                Sons[ticket[0]].append(ticket[1])\n",
    "            else:\n",
    "                Sons[ticket[0]] = [ticket[1]]\n",
    "        for son in Sons:\n",
    "            Sons[son] = sorted(Sons[son])\n",
    "\n",
    "        St = []\n",
    "        dfs(\"JFK\")\n",
    "        return St[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        d = defaultdict(list)\n",
    "        havetickets = defaultdict(int)\n",
    "    \n",
    "        for a,b in tickets:\n",
    "            d[a].append(b)\n",
    "            havetickets[a+b] += 1\n",
    "        for k in d.keys():\n",
    "            d[k] = list(set(d[k]))\n",
    "            d[k].sort()\n",
    "\n",
    "        reach = [\"JFK\"]\n",
    "        res = []\n",
    "    \n",
    "        def travel(begin,use):\n",
    "            if use == 0:\n",
    "                res.append(reach.copy())\n",
    "                return True\n",
    "\n",
    "            for pos in d[begin]:\n",
    "                if havetickets[begin+pos] == 0:\n",
    "                    continue\n",
    "                \n",
    "                reach.append(pos)\n",
    "                havetickets[begin+pos] -= 1\n",
    "                if travel(pos,use-1):\n",
    "                    return True\n",
    "                havetickets[begin+pos] += 1\n",
    "                reach.pop()\n",
    "            \n",
    "            return False\n",
    "\n",
    "        travel(reach[-1],len(tickets))\n",
    " \n",
    "        return res[0]\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        \"\"\"\n",
    "        欧拉回路问题\n",
    "        Hierholzer 算法\n",
    "            从起点出发，进行深度优先搜索。\n",
    "\n",
    "            每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边。\n",
    "\n",
    "            如果没有可移动的路径，则将所在节点加入到栈中，并返回。\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        def dfs(curr):\n",
    "            # 先搜索后入栈防止先对死胡同进行搜索\n",
    "            while vec[curr]:\n",
    "                tmp = heapq.heappop(vec[curr])\n",
    "                dfs(tmp)\n",
    "            stack.append(curr)\n",
    "        \n",
    "        # 构建字典，出发点为key, value为到达机场的小根堆\n",
    "        vec = collections.defaultdict(list)\n",
    "        for depart, arrive in tickets:\n",
    "            vec[depart].append(arrive)\n",
    "        for key in vec:\n",
    "            heapq.heapify(vec[key])\n",
    "\n",
    "        stack = list()\n",
    "        dfs(\"JFK\")\n",
    "\n",
    "        return stack[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        from collections import defaultdict\n",
    "        ticket_dict = defaultdict(list)\n",
    "        for item in tickets:\n",
    "            ticket_dict[item[0]].append(item[1])\n",
    "\n",
    "        path = ['JFK']\n",
    "\n",
    "        def backtrack(cur_from):\n",
    "            if len(path) == len(tickets) + 1:  # 结束条件\n",
    "                return True\n",
    "            ticket_dict[cur_from].sort()\n",
    "            for _ in ticket_dict[cur_from]:\n",
    "                cur_to = ticket_dict[cur_from].pop(0)  # 删除当前节点\n",
    "                path.append(cur_to)  # 做选择\n",
    "                if backtrack(cur_to):  # 进入下一层决策树\n",
    "                    return True\n",
    "                path.pop()  # 取消选择\n",
    "                ticket_dict[cur_from].append(cur_to)  # 恢复当前节点\n",
    "            return False\n",
    "\n",
    "        backtrack('JFK')\n",
    "        return path\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findItinerary(self, tickets: list[list[str]]) -> list[str]:\r\n",
    "        ## 就是从JFK出发，到达所有站点，并且取排序靠前的路径 但是所有机票都要用掉\r\n",
    "        # 站点是可以重复的 但是机票不能重复使用 有向表 回溯，所有不能用used记录访问情况\r\n",
    "        \r\n",
    "        # 机票需要被记录使用情况\r\n",
    "        # used = [False] * length\r\n",
    "        # 已知出发点 \r\n",
    "        # result = []\r\n",
    "        # path = []\r\n",
    "        # city = []\r\n",
    "        # for i in tickets:\r\n",
    "        #     if i[0] not in city:\r\n",
    "        #         city.append(i[0])\r\n",
    "        #     if i[1] not in city:\r\n",
    "        #         city.append(i[1])\r\n",
    "        # length = max(len(city),len(tickets))\r\n",
    "        # def creatGraph(city, tickets):\r\n",
    "        #     graph = [[] for _ in range(len(city))]\r\n",
    "        #     for i in tickets:\r\n",
    "        #         for j in range(len(city)):\r\n",
    "        #             if i[0] == city[j]:\r\n",
    "        #                 graph[j].append(i[1])   # 在加入的时候，或者构建graph的时候，就应该先排序，要小字母在前\r\n",
    "        #                 continue\r\n",
    "        #     return graph\r\n",
    "\r\n",
    "\r\n",
    "        # graph = creatGraph(city, tickets)   #邻接表\r\n",
    "\r\n",
    "        # def dfs(path, used, ticket, temp_city):\r\n",
    "        #     nonlocal tickets, result, graph\r\n",
    "        #     flag = 0\r\n",
    "        #     for i in used:\r\n",
    "        #         if False in i:\r\n",
    "        #             flag = 1\r\n",
    "        #             break\r\n",
    "        #     if not flag:   #全部使用\r\n",
    "        #         result.append(path[:])\r\n",
    "        #         return\r\n",
    "            \r\n",
    "        #     # used = [False for _ in range(len(graph[id]))]\r\n",
    "        #     id = city.index(temp_city)\r\n",
    "        #     for i in graph[id]:   # 一个邻接表 graph[id]   i 城市\r\n",
    "        #         # if False not in used:   #已经全部被用过了\r\n",
    "        #         #     return\r\n",
    "        #         if used[id][graph[id].index(i)] == True:\r\n",
    "        #             continue\r\n",
    "        #         path.append(i)\r\n",
    "        #         ticket += 1\r\n",
    "        #         used[id][graph[id].index(i)] = True\r\n",
    "        #         dfs(path, used, ticket, i)\r\n",
    "        #         path.pop()\r\n",
    "        #         ticket -= 1\r\n",
    "        #         used[id][graph[id].index(i)] = False\r\n",
    "        # used = []\r\n",
    "        # for i in graph:\r\n",
    "        #     used.append([False for _ in range(len(i))])\r\n",
    "        # dfs(['JFK'], used, 1, 'JFK')    ###  因为\r\n",
    "        # ## 剩下排序 需要使用lambda函数\r\n",
    "        # result.sort()\r\n",
    "        # return result[0]\r\n",
    "\r\n",
    "                \r\n",
    "\r\n",
    "\r\n",
    "    \r\n",
    "\r\n",
    "        # ## 根据多组组合得到路线，首先一定从JFK开始\r\n",
    "        # # 给所有组合一个标注 used，表征其是否被用过\r\n",
    "        # # 需要减枝\r\n",
    "        # used = [False]*len(tickets)\r\n",
    "        # path = []\r\n",
    "        # result = []\r\n",
    "        # #path为一条路，result为所有可能结果，只有一个结果时直接输出，否则需要通过排序 ord(symbol)可以排序 lambda函数\r\n",
    "        # def backtracking(ticket, used):\r\n",
    "        #     nonlocal path, result\r\n",
    "        #     if len(path) == len(ticket) + 1:\r\n",
    "        #         result.append(path[:])\r\n",
    "        #     #循环从0开始\r\n",
    "        #     for i in range(0, len(ticket)):\r\n",
    "        #         if len(path) == 0:      #开始时，加入起点\r\n",
    "        #             if ticket[i][0] == 'JFK':\r\n",
    "        #                 path.append(ticket[i][0])\r\n",
    "        #                 path.append(ticket[i][1])\r\n",
    "        #                 used[i] = True\r\n",
    "        #             else:\r\n",
    "        #                 continue\r\n",
    "        #         else:\r\n",
    "        #             if path[-1] == ticket[i][0] and used[i] == False:  \r\n",
    "        #                 #已经得到的路径的最后一个地点等于代取的出发点，并且没有被用过\r\n",
    "        #                 # path.append(ticket[i][0])\r\n",
    "        #                 path.append(ticket[i][1])\r\n",
    "        #                 used[i] = True\r\n",
    "        #             else:\r\n",
    "        #                 continue\r\n",
    "        #         backtracking(ticket, used)\r\n",
    "        #         path.pop()\r\n",
    "        #         used[i] = False\r\n",
    "        # backtracking(tickets, used)\r\n",
    "        # result = sorted(result)\r\n",
    "        # return result[0]\r\n",
    "        ## 上面是自己写的回溯，但是赘余很多，在第11组时出现了超时\r\n",
    "\r\n",
    "\r\n",
    "        ####### \r\n",
    "        from collections import defaultdict\r\n",
    "        #defaultdict(list) 为了方便直接append\r\n",
    "        tickets_dict = defaultdict(list)\r\n",
    "        for item in tickets:\r\n",
    "            tickets_dict[item[0]].append(item[1])    #####\r\n",
    "\r\n",
    "        # 给每一个机场的到达机场排序，小的在前面，在回溯里，首先被pop（）出去\r\n",
    "        # 这样最先得到的path就是排序最小的答案，可以直接返回\r\n",
    "        for airport in tickets_dict: \r\n",
    "            tickets_dict[airport].sort()   ####！！！！！ 对机场进行排序\r\n",
    "            '''\r\n",
    "            ticket_dict 中的内容是这样的：\r\n",
    "            {'JFK':['ATL','SFO'],'SFO':['ATL'],'ATL':['JFK','SFO']}   有映射关系，而且已经排序\r\n",
    "            '''\r\n",
    "        path = ['JFK']\r\n",
    "        def breaktracking(start_point):\r\n",
    "            nonlocal path,tickets_dict\r\n",
    "            if len(path) == len(tickets) + 1:   #### 回溯终止条件 是走过的机场 位 机票+1\r\n",
    "                return True\r\n",
    "            for i in tickets_dict[start_point]:\r\n",
    "                # 必须及时删除，避免出现死循环\r\n",
    "                end_point = tickets_dict[start_point].pop(0)   #机票到达点\r\n",
    "                path.append(end_point)\r\n",
    "                # 回溯，只需要一个满足就直接返回\r\n",
    "                if breaktracking(end_point):\r\n",
    "                    return True\r\n",
    "                path.pop()\r\n",
    "                tickets_dict[start_point].append(end_point)\r\n",
    "        breaktracking('JFK')\r\n",
    "        return path\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        from collections import defaultdict\n",
    "        ticket_dict = defaultdict(list)\n",
    "        for item in tickets:\n",
    "            ticket_dict[item[0]].append(item[1])\n",
    "\n",
    "        path = ['JFK']\n",
    "\n",
    "        def backtrack(cur_from):\n",
    "            if len(path) == len(tickets) + 1:  # 结束条件\n",
    "                return True\n",
    "            ticket_dict[cur_from].sort()\n",
    "            for _ in ticket_dict[cur_from]:\n",
    "                cur_to = ticket_dict[cur_from].pop(0)  # 删除当前节点\n",
    "                path.append(cur_to)  # 做选择\n",
    "                if backtrack(cur_to):  # 进入下一层决策树\n",
    "                    return True\n",
    "                path.pop()  # 取消选择\n",
    "                ticket_dict[cur_from].append(cur_to)  # 恢复当前节点\n",
    "            return False\n",
    "\n",
    "        backtrack('JFK')\n",
    "        return path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        tickets.sort()\n",
    "        adj = {}\n",
    "        for e, v in tickets:\n",
    "            if e not in adj: adj[e] = []\n",
    "            adj[e].append(v)\n",
    "\n",
    "        res = ['JFK']\n",
    "        def dfs(city, used):\n",
    "            if used == len(tickets):\n",
    "                 return True\n",
    "            if city not in adj:\n",
    "                return False\n",
    "            temp = list(adj[city])\n",
    "            for i, v in enumerate(temp):\n",
    "                adj[city].pop(i)\n",
    "                res.append(v)\n",
    "                if dfs(v, used + 1): return True\n",
    "                adj[city].insert(i, v)\n",
    "                res.pop()\n",
    "            return False\n",
    "        dfs('JFK', 0)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        n=len(tickets)\n",
    "        # 根据字母排序\n",
    "        tickets.sort()\n",
    "        dict1=defaultdict(list)\n",
    "        for i in tickets:\n",
    "            dict1[i[0]].append(i[1])\n",
    "        # 建立路径  \n",
    "        path=['JFK']\n",
    "\n",
    "        def backtrack(cur_from):\n",
    "            # 结束条件\n",
    "            if len(path)==len(tickets)+1:\n",
    "                return True\n",
    "            # 排序最初的出发地\n",
    "            dict1[cur_from].sort()\n",
    "            for _ in dict1[cur_from]:\n",
    "                # 删除当前第一个节点\n",
    "                cur_to = dict1[cur_from].pop(0)\n",
    "                # 在路径中加入cur to\n",
    "                path.append(cur_to)\n",
    "                # 递归第一个目的地当成出发点，如果有则继续\n",
    "                if backtrack(cur_to):\n",
    "                    return True\n",
    "                #没有的话， 将其从path中取出\n",
    "                path.pop()\n",
    "                # 恢复当前节点\n",
    "                dict1[cur_from].append(cur_to)\n",
    "            # 此处回溯是失败的\n",
    "            return False\n",
    "        backtrack('JFK')\n",
    "        return path\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        mapa = collections.defaultdict(list)\n",
    "        ans = [\"JFK\"]\n",
    "\n",
    "        for ticket in tickets:\n",
    "            mapa[ticket[0]].append(ticket[1])\n",
    "\n",
    "        for key in mapa.keys():\n",
    "            mapa[key].sort()\n",
    "\n",
    "        print(mapa)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        def dfs(f):\n",
    "            while mapa[f]:\n",
    "                dfs(mapa[f].pop(0))\n",
    "            ans.insert(0,f)\n",
    "\n",
    "        dfs(\"JFK\")\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        fromTo ={}\n",
    "        for t in tickets:\n",
    "            if t[0] in fromTo:\n",
    "                fromTo[t[0]].append(t[1])\n",
    "            else:\n",
    "                fromTo[t[0]]=[t[1]]\n",
    "        \n",
    "        for k in fromTo.keys():\n",
    "            fromTo[k].sort()\n",
    "        \n",
    "\n",
    "        self.res=[]\n",
    "        self.n=len(tickets)\n",
    "        print(fromTo)\n",
    "        def dfs(path,candidates):\n",
    "            # print(path, candidates)\n",
    "            if len(candidates)==0:\n",
    "                self.res.append(path)\n",
    "                return True\n",
    "            \n",
    "            if path[-1] not in fromTo:\n",
    "                return False\n",
    "            for to in fromTo[path[-1]]:\n",
    "                if [path[-1],to] in candidates:\n",
    "                    candidates.remove([path[-1],to])\n",
    "                    if dfs(path+[to],candidates):\n",
    "                        return True\n",
    "                    candidates.append([path[-1],to])\n",
    "        dfs(['JFK'],tickets)\n",
    "        self.res.sort()\n",
    "        # print(self.res)\n",
    "        return self.res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        dic = defaultdict(list)\n",
    "        count = 0\n",
    "        she = {}\n",
    "        tickets.sort()\n",
    "        for i,j in tickets:\n",
    "            dic[i].append(j)\n",
    "            if i not in she:\n",
    "                she[i] = count\n",
    "                count+=1\n",
    "            if j not in she:\n",
    "                she[j] = count\n",
    "                count+=1\n",
    "        save = [[0]*count for _ in range(count)]\n",
    "        for i,j in tickets:\n",
    "            save[she[i]][she[j]]+=1\n",
    "        res = []\n",
    "        n = len(tickets)\n",
    "        def dfs(i,temp):\n",
    "            temp.append(i)\n",
    "            if len(temp)==n+1:\n",
    "                # print(temp)\n",
    "                res.append(temp.copy())\n",
    "                return True\n",
    "            used = {}\n",
    "            for x in dic[i]:\n",
    "                if save[she[i]][she[x]]>0 and x not in used:\n",
    "                    save[she[i]][she[x]]-=1\n",
    "                    status = dfs(x,temp)\n",
    "                    if status:\n",
    "                        return True\n",
    "                    save[she[i]][she[x]]+=1\n",
    "                    used[x] = 1\n",
    "            temp.pop()\n",
    "            return False\n",
    "        dfs(\"JFK\",[])\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        # def backtracking(tickets, used, path, cur, results):\n",
    "        #     if len(path) == len(tickets) + 1: \n",
    "        #         # 终止条件：路径长度等于机票数量+1\n",
    "        #         results.append(path[:])\n",
    "        #         # 将当前路径添加到结果列表\n",
    "        #         return True\n",
    "\n",
    "        #     for i, ticket in enumerate(tickets):#遍历机票列表\n",
    "        #         if ticket[0] == cur and used[i] == 0:\n",
    "        #             #找到起始机场cur，未使用过的机票\n",
    "        #             used[i] = 1\n",
    "        #             path.append(ticket[1])\n",
    "        #             state = backtracking(tickets, used, path, ticket[1], results)\n",
    "        #             path.pop()\n",
    "        #             used[i] = 0\n",
    "        #             #标记改机票未使用\n",
    "        #             if state:\n",
    "        #                 return True#只要找到一个路径就可以返回，不继续搜索\n",
    "        \n",
    "        # tickets.sort() # 先排序，这样一旦找到第一个可行路径，一定是字母排序最小的\n",
    "        # used = [0] * len(tickets)\n",
    "        # path = ['JFK']\n",
    "        # results = []\n",
    "        # backtracking(tickets, used, path, 'JFK', results)\n",
    "        # return results[0]\n",
    "\n",
    "\n",
    "\n",
    "        from collections import defaultdict\n",
    "        ticket_dict = defaultdict(list)\n",
    "        for item in tickets:\n",
    "            ticket_dict[item[0]].append(item[1])\n",
    "        \n",
    "        path = ['JFK']\n",
    "        def backtracking(cur_from):\n",
    "            if len(path) == len(tickets) + 1:\n",
    "                return True\n",
    "            ticket_dict[cur_from].sort()\n",
    "            for _ in ticket_dict[cur_from]:\n",
    "                cur_to = ticket_dict[cur_from].pop(0)\n",
    "                path.append(cur_to)\n",
    "                if backtracking(cur_to):\n",
    "                    return True\n",
    "                path.pop()\n",
    "                ticket_dict[cur_from].append(cur_to)\n",
    "            return False\n",
    "        \n",
    "        backtracking('JFK')\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        path_record = defaultdict(list)\n",
    "\n",
    "        for _from, _to in tickets:\n",
    "            path_record[_from].append(_to)\n",
    "\n",
    "\n",
    "        result = []\n",
    "        path = []\n",
    "\n",
    "        def traverse(start_node):\n",
    "            path.append(start_node)\n",
    "            if len(path) == len(tickets) + 1:\n",
    "                result.append(path[:])\n",
    "                return True\n",
    "\n",
    "            if start_node not in path_record:\n",
    "                return False\n",
    "            paths = sorted(set(path_record.get(start_node)))\n",
    "            for node in paths:\n",
    "                path_record[start_node].remove(node)\n",
    "                if traverse(node):\n",
    "                    return True\n",
    "                path.pop()\n",
    "                path_record[start_node].append(node)\n",
    "            return False\n",
    "        return result[0] if traverse(start_node='JFK') else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        n = len(tickets)\n",
    "        ans = []\n",
    "        used = [False for _ in range(n)]\n",
    "\n",
    "        def backtrack(path, start, used) -> bool:\n",
    "            nonlocal ans\n",
    "            if len(path) == n+1:\n",
    "                ans = path[:]\n",
    "                return True\n",
    "            \n",
    "            choices = []        # 可以选择的车票到达站\n",
    "            for i, ticket in enumerate(tickets):\n",
    "                if ticket[0] == start and used[i] == False:\n",
    "                    choices.append((ticket[1], i))\n",
    "            choices.sort()\n",
    "            for end, i in choices:\n",
    "                path.append(end)\n",
    "                used[i] = True\n",
    "                if backtrack(path, end, used):\n",
    "                    return True\n",
    "                used[i] = False\n",
    "                path.pop()\n",
    "        backtrack([\"JFK\"], \"JFK\", used)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result=[]\n",
    "    def backtrace(self,tickets,path):\n",
    "        if len(tickets)==0:\n",
    "            self.result=path\n",
    "            return True\n",
    "        if len(path)==0:\n",
    "            start=\"JFK\"\n",
    "            path.append(\"JFK\")\n",
    "        else:\n",
    "            start=path[len(path)-1]\n",
    "        for i,ticket in enumerate(tickets):\n",
    "            if ticket[0]==start:\n",
    "                if(self.backtrace(tickets[:i]+tickets[i+1:],path+[ticket[1]])):\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        tickets=sorted(tickets, key=lambda x:x[1])\n",
    "        self.backtrace(tickets,[])\n",
    "        return self.result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        dic = {}\n",
    "        res = None\n",
    "        for ticket in tickets:\n",
    "            if ticket[0] not in dic:\n",
    "                dic[ticket[0]] = [ticket[1]]\n",
    "                if ticket[1] not in dic:\n",
    "                    dic[ticket[1]] = []\n",
    "            else:\n",
    "                dic[ticket[0]].append(ticket[1])\n",
    "                if ticket[1] not in dic:\n",
    "                    dic[ticket[1]] = []\n",
    "        for key in dic.keys():\n",
    "            dic[key] = sorted(dic[key])\n",
    "        def dfs(path, cur, dic) -> None:\n",
    "            nonlocal res\n",
    "            if len(dic[cur]) == 0 and len(path) == len(tickets) + 1:\n",
    "                if res is None:\n",
    "                    res = path[:]\n",
    "                return\n",
    "            elif len(dic[cur]) == 0:\n",
    "                return\n",
    "            else:\n",
    "                pre = []\n",
    "                for i in range(len(dic[cur])):\n",
    "                    if dic[cur][i] not in pre:\n",
    "                        path.append(dic[cur][i])\n",
    "                        dic[cur].pop(i)\n",
    "                        dfs(path, path[-1], dic)\n",
    "                        if res is not None:\n",
    "                            return res\n",
    "                        dic[cur].insert(i, path.pop())\n",
    "                        pre.append(dic[cur][i])\n",
    "        dfs(['JFK'], 'JFK', dic)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets):\n",
    "        from collections import defaultdict\n",
    "        ticket_dict = defaultdict(list)\n",
    "        for item in tickets:\n",
    "            ticket_dict[item[0]].append(item[1])\n",
    "        for x in ticket_dict:\n",
    "            ticket_dict[x].sort()\n",
    "        path = ['JFK']\n",
    "\n",
    "        def backtrack(cur_from):\n",
    "            if len(path) == len(tickets) + 1:  # 结束条件\n",
    "                return True\n",
    "            \n",
    "            for _ in ticket_dict[cur_from]:\n",
    "                cur_to = ticket_dict[cur_from].pop(0)  # 删除当前节点\n",
    "                path.append(cur_to)  # 做选择\n",
    "                if backtrack(cur_to):  # 进行递归调用\n",
    "                    return True\n",
    "                path.pop()  # 取消选择\n",
    "                ticket_dict[cur_from].append(cur_to)  # 恢复当前节点\n",
    "            return False\n",
    "\n",
    "        backtrack('JFK')\n",
    "        return path\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "  \n",
    "        \n",
    "\n",
    "                \n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        dic = defaultdict(list)\n",
    "        for ticket in tickets:\n",
    "            dic[ticket[0]].append(ticket[1])\n",
    "        n = len(tickets)\n",
    "        seen = set()\n",
    "        # def backtrack(start, num, path):\n",
    "        #     if num == 0:\n",
    "        #         # res.append(path[:])\n",
    "        #         return True\n",
    "        #     dic[start].sort()\n",
    "        #     for  _ in (dic[start]):\n",
    "        #         cur = dic[start].pop(0)\n",
    "        #         path.append(cur)\n",
    "        #         if backtrack(cur, num-1, path):\n",
    "        #             return True\n",
    "        #         # backtrack(cur, num-1, path)\n",
    "        #         path.pop()\n",
    "        #         dic[start].append(cur)\n",
    "\n",
    "        def backtrack(start, num, path):\n",
    "            if num == 0:\n",
    "                return True \n",
    "            dic[start].sort()\n",
    "            for index, i in enumerate(dic[start]):\n",
    "                if (start, i, index) in seen:\n",
    "                    continue\n",
    "                seen.add((start, i, index))\n",
    "                path.append(i)\n",
    "                if backtrack(i, num-1, path):\n",
    "                    return True\n",
    "                path.pop()\n",
    "                seen.remove((start, i, index))\n",
    "\n",
    "        path = ['JFK']     \n",
    "        backtrack('JFK', n, path)\n",
    "\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:  # official\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        from collections import defaultdict\n",
    "        graph = defaultdict(list)\n",
    "        for f, t in tickets:\n",
    "            graph[f].append(t)\n",
    "        \n",
    "        for f in graph:\n",
    "            graph[f].sort()\n",
    "        \n",
    "        path = [\"JFK\"]\n",
    "        \n",
    "        def backtracking(start_point):\n",
    "            if len(path) == len(tickets) + 1:\n",
    "                return True\n",
    "            \n",
    "            for _ in graph[start_point]:\n",
    "                end_point = graph[start_point].pop(0)\n",
    "                path.append(end_point)\n",
    "                if backtracking(end_point):\n",
    "                    return True\n",
    "                path.pop()\n",
    "                graph[start_point].append(end_point) \n",
    "                '''\n",
    "                    myhuang_note_68: \n",
    "                    'JFK': ['KUL', 'NRT']\n",
    "                    'NRT': ['JFK']\n",
    "                    a.Because it indicates that there must be a path, the pop element in the path is placed at the end of the list.\n",
    "                    b.The elements in the last of the list still stayed in sorted.\n",
    "\n",
    "                    https://leetcode.cn/problems/reconstruct-itinerary/solution/zhong-xin-an-pai-xing-cheng-by-leetcode-solution/\n",
    "                '''\n",
    "        \n",
    "        backtracking(\"JFK\")\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        tickets = sorted(tickets)\n",
    "        ticket_num = len(tickets)\n",
    "        result = []\n",
    "        path = []\n",
    "        def backtracking(tickets, start):\n",
    "            if result:\n",
    "                return\n",
    "\n",
    "            length = len(tickets)\n",
    "            if length == 0:\n",
    "                new_result = [\"JFK\"] + [ticket[1] for ticket in path]\n",
    "                result.extend(new_result)\n",
    "                return\n",
    "            else:\n",
    "                pre = None\n",
    "                for i in range(length):\n",
    "                    if pre and pre == tickets[i]:\n",
    "                        continue\n",
    "                    pre = tickets[i]\n",
    "                    if tickets[i][0] != start:\n",
    "                        continue\n",
    "                    path.append(tickets[i])\n",
    "                    backtracking(tickets[:i]+tickets[i+1:], tickets[i][1])\n",
    "                    path.pop()\n",
    "\n",
    "\n",
    "        backtracking(tickets, \"JFK\")\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        #先找到所有从JFK出发的机票，考察到达目的后有几种选择\n",
    "        #相当于没有目的地固定，但是有起点固定，飞就完了\n",
    "        #有效的线路的长度等于tickets，且每个机票都有且只用过一次\n",
    "\n",
    "        # air_set = {}\n",
    "        # for i in tickets:\n",
    "        #     if i[0] not in air_set:\n",
    "        #         air_set[i[0]] = [i[1]]\n",
    "        #     else:\n",
    "        #         air_set[i[0]].append(i[1])\n",
    "        # #对每个机场的可能目的地进行字典序排序  \n",
    "        # for i in air_set:\n",
    "        #     air_set[i] = sorted(air_set[i])\n",
    "        # print(air_set)\n",
    "\n",
    "        # route = []\n",
    "        # routes = []\n",
    "        # length = len(air_set)\n",
    "        # def dfs(route, air_set):\n",
    "        # #     print(route)\n",
    "        #     #合法的输出结果\n",
    "        #     if len(route) == len(tickets) + 1:\n",
    "        #         if len(routes) == 0:\n",
    "        #             routes.append(route[:])\n",
    "        #         else:\n",
    "        #             routes.pop()\n",
    "        #             routes.append(route[:])\n",
    "        # #             print(routes)\n",
    "        #         return\n",
    "            \n",
    "        #     #从最小字典序的序列开始考察，一旦找到了一个合法的就结束程序\n",
    "        #     if len(routes) == 0:\n",
    "        # #         print(route)\n",
    "        #         #第一程飞机得从\"JFK\"出发\n",
    "        #         if len(route) == 0:\n",
    "        #             route.append(\"JFK\")\n",
    "        #             for i in range(len(air_set[\"JFK\"])):\n",
    "        #                 if len(routes) == 0:\n",
    "        #                     route.append(air_set[\"JFK\"][i])\n",
    "        #                     del air_set[\"JFK\"][i]\n",
    "        #     #                 print(route)\n",
    "        #                     dfs(route, air_set)\n",
    "        #                     air_set[\"JFK\"].insert(i, route[-1])\n",
    "        #     #                 print(route)\n",
    "        #                     route.pop()\n",
    "        #             route.pop()\n",
    "        #         #route 已经有东西的情况 \n",
    "        #         else:\n",
    "        # #             print(route)\n",
    "        #             if route[-1] in air_set:\n",
    "        #                 for i in range(len(air_set[route[-1]])):\n",
    "        #                     if len(routes) == 0:\n",
    "        #                         route.append(air_set[route[-1]][i])\n",
    "        #                         del air_set[route[-2]][i]\n",
    "        #                         dfs(route, air_set)\n",
    "        #                         air_set[route[-2]].insert(i, route[-1])\n",
    "        #                         route.pop() \n",
    "        #     #考察完没有合法的\n",
    "        #     return\n",
    "        # dfs(route, air_set)\n",
    "        # return routes[0]\n",
    "        \n",
    "        # import copy\n",
    "        #列出从每一个机场出发可能的所有的目的机场\n",
    "        # air_set = {}\n",
    "        # for i in tickets:\n",
    "        #     if i[0] not in air_set:\n",
    "        #         air_set[i[0]] = [i[1]]\n",
    "        #     else:\n",
    "        #         air_set[i[0]].append(i[1])\n",
    "        # #对每个机场的可能目的地进行字典序排序  \n",
    "        # for i in air_set:\n",
    "        #     air_set[i] = sorted(air_set[i])\n",
    "        # # print(air_set)\n",
    "\n",
    "        # #计算有每个机场有几个航班是从该机场出发和到达该机场的。\n",
    "        # departs_set = {}\n",
    "        # for i in air_set:\n",
    "        #     departs_set[i] = len(air_set[i])\n",
    "        # arrival_set = {}\n",
    "        # for i in tickets:\n",
    "        #     if i[1] not in arrival_set:\n",
    "        #         arrival_set[i[1]] = 1\n",
    "        #     else:\n",
    "        #         arrival_set[i[1]] += 1\n",
    "        # for i in departs_set:\n",
    "        #     if i not in arrival_set:\n",
    "        #         arrival_set[i] = 0\n",
    "\n",
    "        # #找终点站\n",
    "        # des = \"\"\n",
    "        # if departs_set[\"JFK\"] != arrival_set[\"JFK\"]:\n",
    "        #     for i in departs_set:\n",
    "        # #         print(departs_set[i] + 1 == arrival_set[i])\n",
    "        #         if i != \"JFK\" and departs_set[i] + 1 == arrival_set[i]:\n",
    "        #             des = i\n",
    "        # else:\n",
    "        #     des = \"JFK\"\n",
    "        # # print(des)\n",
    "\n",
    "        # #不管des是谁，把它在JFK里面的的机票挪到最后\n",
    "        # if des in air_set[\"JFK\"]:\n",
    "        #     for j in range(len(air_set[\"JFK\"])):\n",
    "        #         if air_set[\"JFK\"][j] == des:\n",
    "        #             air_set[\"JFK\"].append(des)\n",
    "        #             del air_set[\"JFK\"][j]\n",
    "        # # print(air_set)\n",
    "\n",
    "        # # #先做一个反过来的air_set_rev\n",
    "        # # tickets_rev = copy.deepcopy(tickets)\n",
    "        # # for i in tickets_rev:\n",
    "        # #     i.reverse()\n",
    "            \n",
    "        # # #列出从每一个机场出发可能的所有的目的机场\n",
    "        # # air_set_rev = {}\n",
    "        # # for i in tickets_rev:\n",
    "        # #     if i[0] not in air_set_rev:\n",
    "        # #         air_set_rev[i[0]] = [i[1]]\n",
    "        # #     else:\n",
    "        # #         air_set_rev[i[0]].append(i[1])\n",
    "        # # #对每个机场的可能目的地进行字典序排序  \n",
    "        # # for i in air_set_rev:\n",
    "        # #     air_set_rev[i] = sorted(air_set_rev[i])\n",
    "        # # # print(air_set_rev)\n",
    "\n",
    "        # # #从JFK反向出发，回溯，看会去到正向出发时，JFK能够最先去哪个机场，从而排除找到不能回JFK的机场，该机场置后 这是针对，JFK不是终点的情况，即JFK回来的次数是去的次数少一次。\n",
    "        # # JFKdes_rev = []\n",
    "        # # JFKdes = air_set[\"JFK\"]\n",
    "        # # sub_des = \"\"\n",
    "        # # def dfs_rev(air_set_rev, sub_des):\n",
    "        # #     if sub_des in JFKdes and sub_des not in JFKdes_rev:\n",
    "        # #         JFKdes_rev.append(sub_des)\n",
    "        # #         return\n",
    "            \n",
    "        # # #     print(sub_des)\n",
    "        # #     if sub_des == \"\":\n",
    "        # #         for i in range(len(air_set_rev[\"JFK\"])):\n",
    "        # #             sub_des = air_set_rev[\"JFK\"][i]\n",
    "        # #             del air_set_rev[\"JFK\"][i]\n",
    "        # #             dfs_rev(air_set_rev, sub_des)\n",
    "        # #             air_set_rev[\"JFK\"].insert(i, sub_des)\n",
    "        # #             sub_des = \"\"\n",
    "        # #     else:\n",
    "        # #         for i in range(len(air_set_rev[sub_des])):\n",
    "        # #             # print(sub_des)\n",
    "        # #             tmp = sub_des\n",
    "        # #             sub_des = air_set_rev[sub_des][i]\n",
    "        # # #             print(sub_des)\n",
    "        # #             del air_set_rev[tmp][i]\n",
    "        # #             dfs_rev(air_set_rev, sub_des)\n",
    "        # #             air_set_rev[tmp].insert(i, sub_des)\n",
    "        # # #             print(air_set_rev)\n",
    "        # #             sub_des = tmp\n",
    "        # #     return\n",
    "                \n",
    "        # # if departs_set[\"JFK\"] > 1:\n",
    "        # #     if departs_set[\"JFK\"] - 1 == arrival_set[\"JFK\"]:\n",
    "        # #         dfs_rev(air_set_rev, sub_des)\n",
    "        # #         if JFKdes_rev:\n",
    "        # #             for i in range(len(JFKdes)):\n",
    "        # #                 if JFKdes[i] not in JFKdes_rev:\n",
    "        # #                     JFKdes.append(JFKdes[i])\n",
    "        # #                     del JFKdes[i]\n",
    "        # #             air_set[\"JFK\"] = JFKdes\n",
    "\n",
    "        # #主体DFS        \n",
    "        # route = []\n",
    "        # routes = []\n",
    "        # length = len(air_set)\n",
    "        # def dfs(route, air_set):\n",
    "        # #     print(air_set)\n",
    "        # #     print(route)\n",
    "        #     #合法的输出结果\n",
    "        #     if len(route) == len(tickets) + 1:\n",
    "        #         if len(routes) == 0:\n",
    "        #             routes.append(route[:])\n",
    "        #         else:\n",
    "        #             routes.pop()\n",
    "        #             routes.append(route[:])\n",
    "        # #             print(routes)\n",
    "        #         return\n",
    "            \n",
    "        #     #从最小字典序的序列开始考察，一旦找到了一个合法的就结束程序\n",
    "        #     if len(routes) == 0:\n",
    "        # #         print(route)\n",
    "        #         #第一程飞机得从\"JFK\"出发\n",
    "        #         if len(route) == 0:\n",
    "        #             route.append(\"JFK\")\n",
    "        #             for i in range(len(air_set[\"JFK\"])):\n",
    "        #                 route.append(air_set[\"JFK\"][i])\n",
    "        #                 del air_set[\"JFK\"][i]\n",
    "        # #                 print(route)\n",
    "        #                 dfs(route, air_set)\n",
    "        #                 air_set[\"JFK\"].insert(i, route[-1])\n",
    "        # #                 print(route)\n",
    "        #                 route.pop()\n",
    "        #             route.pop()\n",
    "        #         #route 已经有东西的情况 \n",
    "        #         else:\n",
    "        # #             print(route)\n",
    "        #             if route[-1] in air_set:\n",
    "        #                 for i in range(len(air_set[route[-1]])):\n",
    "        #                     route.append(air_set[route[-1]][i])\n",
    "        #                     del air_set[route[-2]][i]\n",
    "        #                     dfs(route, air_set)\n",
    "        #                     air_set[route[-2]].insert(i, route[-1])\n",
    "        #                     route.pop() \n",
    "        #     #考察完没有合法的\n",
    "        #     return\n",
    "\n",
    "        # dfs(route, air_set)\n",
    "        # # return routes[0]\n",
    "        # JFKdes = sorted(air_set[\"JFK\"])\n",
    "        # for i in JFKdes:\n",
    "        #     if i < routes[0][1]:\n",
    "        #         #考察是否有环路包含JFK\n",
    "        #         index_i = [index1 for index1,value in enumerate(routes[0]) if value == i]\n",
    "        #         index_JFK = [index1 for index1,value in enumerate(routes[0]) if value == \"JFK\"]\n",
    "        #         if len(index_i) >= 2:\n",
    "        #             for j in index_JFK:\n",
    "        #                 if j>index_i[0] and j < index_i[-1]:\n",
    "        #                     #有环路且包含JFK，搞一下\n",
    "        #                     route_bk = copy.deepcopy(route)\n",
    "        #                     routes_bk = copy.deepcopy(routes)\n",
    "        #                     JFKdes_bk = copy.deepcopy(air_set[\"JFK\"])\n",
    "        #                     air_set[\"JFK\"][air_set[\"JFK\"].index(i)], air_set[\"JFK\"][air_set[\"JFK\"].index(routes[0][1])] =\\\n",
    "        #                     air_set[\"JFK\"][air_set[\"JFK\"].index(routes[0][1])], air_set[\"JFK\"][air_set[\"JFK\"].index(i)]\n",
    "        #                     route = []\n",
    "        #                     routes = []\n",
    "        #                     dfs(route, air_set)\n",
    "        #                     if routes:\n",
    "        #                         routes[0]\n",
    "        #                         return routes[0]\n",
    "        #                     else:\n",
    "        #                         route = route_bk\n",
    "        #                         routes = routes_bk\n",
    "        #                         air_set[\"JFK\"] = JFKdes_bk\n",
    "        # return routes[0]\n",
    "        def dfs(ticket):\n",
    "            print(ticket)\n",
    "            print(Sons)\n",
    "            #把没有从该地方出发的机场加进St里(有可能所有机场都有出发，也可能有没有的)\n",
    "            if (ticket not in Sons):\n",
    "                St.append(ticket)\n",
    "                return 0\n",
    "            \n",
    "            while (Sons[ticket]):\n",
    "                tmp = Sons[ticket][0]\n",
    "                Sons[ticket].pop(0)\n",
    "                dfs(tmp)\n",
    "            St.append(ticket)\n",
    "            print(St)\n",
    "            return 0\n",
    "            \n",
    "        #类似于我的air_set，构建字典，并对每个item的val按字典序排序\n",
    "        Sons = {}\n",
    "        n = len(tickets)\n",
    "        for ticket in tickets:\n",
    "            if (ticket[0] in Sons):\n",
    "                Sons[ticket[0]].append(ticket[1])\n",
    "            else:\n",
    "                Sons[ticket[0]] = [ticket[1]]\n",
    "        for son in Sons:\n",
    "            Sons[son] = sorted(Sons[son])\n",
    "            \n",
    "        St =[]\n",
    "        dfs(\"JFK\")\n",
    "        return St[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        d = defaultdict(list)\n",
    "        for f, t in tickets:\n",
    "            d[f].append(t)\n",
    "        for k, v in d.items():\n",
    "            d[k] = sorted(v)\n",
    "        res = [\"JFK\"]\n",
    "        def search(pos):\n",
    "            if len(tickets) == len(res)-1:\n",
    "                return True\n",
    "            for idx, to in enumerate(d[pos]):\n",
    "                if to == \"_\":\n",
    "                    continue\n",
    "                else:\n",
    "                    res.append(to)\n",
    "                    d[pos][idx] = \"_\"\n",
    "                    if search(to) == True:\n",
    "                        return True\n",
    "                    else:\n",
    "                        res.pop()\n",
    "                        d[pos][idx] = to\n",
    "            return False\n",
    "        search(\"JFK\")\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        dic = {}\n",
    "        res = None\n",
    "        for ticket in tickets:\n",
    "            if ticket[0] not in dic:\n",
    "                dic[ticket[0]] = [ticket[1]]\n",
    "                if ticket[1] not in dic:\n",
    "                    dic[ticket[1]] = []\n",
    "            else:\n",
    "                dic[ticket[0]].append(ticket[1])\n",
    "                if ticket[1] not in dic:\n",
    "                    dic[ticket[1]] = []\n",
    "        for key in dic.keys():\n",
    "            dic[key] = sorted(dic[key])\n",
    "        def dfs(path, cur, dic) -> None:\n",
    "            nonlocal res\n",
    "            if len(dic[cur]) == 0 and len(path) == len(tickets) + 1:\n",
    "                if res is None:\n",
    "                    res = path[:]\n",
    "                return\n",
    "            elif len(dic[cur]) == 0:\n",
    "                return\n",
    "            else:\n",
    "                pre = []\n",
    "                for i in range(len(dic[cur])):\n",
    "                    if dic[cur][i] not in pre:\n",
    "                        path.append(dic[cur][i])\n",
    "                        dic[cur].pop(i)\n",
    "                        dfs(path, path[-1], dic)\n",
    "                        if res is not None:\n",
    "                            return res\n",
    "                        dic[cur].insert(i, path.pop())\n",
    "                        pre.append(dic[cur][i])\n",
    "        dfs(['JFK'], 'JFK', dic)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        map = {}\n",
    "\n",
    "        for i in range(len(tickets)):\n",
    "            if map.get(tickets[i][0]) is None:\n",
    "                map[tickets[i][0]] = []\n",
    "            map[tickets[i][0]].append(tickets[i][1])\n",
    "        for i in range(len(tickets)):\n",
    "            map[tickets[i][0]].sort()\n",
    "\n",
    "        print(map)\n",
    "\n",
    "        def dfs(start: string):\n",
    "            if len(ans) > len(tickets):\n",
    "                return True\n",
    "            if map.get(start) is None:\n",
    "                return False\n",
    "            destination = map[start]\n",
    "            for i, dest in enumerate(destination):\n",
    "                end = destination[i]\n",
    "                map[start].pop(i)\n",
    "                ans.append(end)\n",
    "                if dfs(end):\n",
    "                    return True\n",
    "                ans.pop()\n",
    "                map[start].insert(i, end)\n",
    "            return False\n",
    "            \n",
    "        ans = [\"JFK\"]\n",
    "        dfs(\"JFK\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        tickets.sort()\n",
    "        hel = [False for i in range(len(tickets))]\n",
    "        def dfs(s,res):\n",
    "            if len(res)==len(tickets)+1:\n",
    "                return res\n",
    "            for i in range(len(tickets)):\n",
    "                if not hel[i] and tickets[i][0]==s:\n",
    "                    hel[i] = True\n",
    "                    r = dfs(tickets[i][1],res+[tickets[i][1]])\n",
    "                    if not r:\n",
    "                        hel[i] = False   \n",
    "                    else:return r\n",
    "        return dfs('JFK',['JFK'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "\n",
    "        tickets.sort() #先排序，选择一旦找到第一个可行路径，一定是字母序最小的\n",
    "        n = len(tickets)\n",
    "        ans = []\n",
    "        path = ['JFK']\n",
    "        used = [False] * n\n",
    "\n",
    "        def dfs(current):\n",
    "\n",
    "            if len(path) == n + 1: #终止条件，路径长度等于机票数量+1\n",
    "                ans.append(path.copy()) #添加结果\n",
    "                return True\n",
    "            \n",
    "            for j, ticket in enumerate(tickets): #遍历机票列表\n",
    "                if ticket[0] == current and not used[j]: #找到起始机场为cur且未使用过的机票\n",
    "                    used[j] = True # 标记该机票为已使用\n",
    "                    path.append(ticket[1]) # 将到达机场添加到路径中， state的作用是判断只需要找到一次即可\n",
    "                    state = dfs(ticket[1]) #递归\n",
    "                    used[j] = False #标记改机票未使用\n",
    "                    path.pop() #回溯\n",
    "\n",
    "                    if state:\n",
    "                        return True #直接返回\n",
    "        dfs('JFK')\n",
    "        return ans[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        city_links = collections.defaultdict(int)\n",
    "        for x, y in tickets: \n",
    "            city_links[(x, y)] += 1\n",
    "            graph[x].append(y)\n",
    "        \n",
    "        \n",
    "        res = ['JFK']\n",
    "        \n",
    "        # returned result should have tickets + 1 cities\n",
    "        def dfs(curr):\n",
    "            if len(res) == len(tickets) + 1:\n",
    "                return True\n",
    "\n",
    "            for dest in sorted(graph[curr]):\n",
    "                if city_links[(curr, dest)] != 0:\n",
    "                    # 尝试这个城市\n",
    "                    city_links[(curr, dest)] -= 1\n",
    "                    res.append(dest)\n",
    "                    if dfs(dest):\n",
    "                        return True\n",
    "                    # 撤销\n",
    "                    res.pop()\n",
    "                    city_links[(curr, dest)] += 1\n",
    "            return False\n",
    "\n",
    "        dfs('JFK')\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        def dfs(path, used):\n",
    "            if len(path) == len(tickets)+1:\n",
    "                res.append(path)\n",
    "                return True\n",
    "            \n",
    "            ignore_set = set()\n",
    "            for i in range(len(tickets)):\n",
    "                cur = tickets[i]\n",
    "                if used[i] or cur[0]!= path[-1] or cur[0]+cur[1] in ignore_set:\n",
    "                    continue\n",
    "                used[i] = 1\n",
    "                state = dfs(path+[cur[1]], used)\n",
    "                used[i]=0\n",
    "                if state:\n",
    "                    return True\n",
    "                else:\n",
    "                    ignore_set.add(cur[0]+cur[1])\n",
    "        \n",
    "        tickets.sort()\n",
    "        res = []\n",
    "        used  = [0]*len(tickets)\n",
    "        dfs(['JFK'], used)\n",
    "        return res[0]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "        def dfs(path, used):\n",
    "            if len(path) == len(tickets)+1:\n",
    "                res.append(path)\n",
    "                return True\n",
    "            \n",
    "            ignore_set = set()\n",
    "            for i in range(len(tickets)):\n",
    "                cur = tickets[i]\n",
    "                if used[i] or cur[0]!= path[-1] or cur[0]+cur[1] in ignore_set:\n",
    "                    continue\n",
    "                used[i] = 1\n",
    "                state = dfs(path+[cur[1]], used)\n",
    "                used[i]=0\n",
    "                if state:\n",
    "                    return True\n",
    "                else:\n",
    "                    ignore_set.add(cur[0]+cur[1])\n",
    "        \n",
    "        tickets.sort()\n",
    "        res = []\n",
    "        used  = [0]*len(tickets)\n",
    "        dfs(['JFK'], used)\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findItinerary(self, tickets: List[List[str]]) -> List[str]:\n",
    "\n",
    "        tickets.sort() #先排序，选择一旦找到第一个可行路径，一定是字母序最小的\n",
    "        n = len(tickets)\n",
    "        ans = []\n",
    "        path = ['JFK']\n",
    "        used = [False] * n\n",
    "\n",
    "        def dfs(current):\n",
    "\n",
    "            if len(path) == n + 1: #终止条件，路径长度等于机票数量+1\n",
    "                ans.append(path.copy()) #添加结果\n",
    "                return True\n",
    "            \n",
    "            for j, ticket in enumerate(tickets): #遍历机票列表\n",
    "                if ticket[0] == current and not used[j]: #找到起始机场为cur且未使用过的机票\n",
    "                    used[j] = True # 标记该机票为已使用\n",
    "                    path.append(ticket[1]) # 将到达机场添加到路径中， state的作用是判断只需要找到一次即可\n",
    "                    state = dfs(ticket[1]) #递归\n",
    "                    used[j] = False #标记改机票未使用\n",
    "                    path.pop() #回溯\n",
    "\n",
    "                    if state:\n",
    "                        return True #直接返回\n",
    "        dfs('JFK')\n",
    "        return ans[0]\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
